package com.LeeCode;

/**
 * 分隔链表
 */

public class Code086 {
    public static void main(String[] args) {
        int[] arr = {1, 4, 3, 2, 5, 2, 4, 3};
        int x = 3;
        ListNode head = Utils.arrayToListNode(arr);
        Utils.printListNode(new Code086().partition(head, x));
    }

    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(0, head), dummy2 = new ListNode(0);
        ListNode cur1 = dummy1, cur2 = dummy2;
        while (cur1.next != null) {
            while (cur1.next != null && cur1.next.val >= x) {
                cur2.next = cur1.next;
                cur2 = cur2.next;
                cur1.next = cur1.next.next;
            }
            cur1 = cur1.next == null ? cur1 : cur1.next;
        }
        cur1.next = dummy2.next;
        cur2.next = null;
        return dummy1.next;
    }
}
